package leetcode.problems.P236二叉树的最近公共祖先;

import java.util.LinkedList;

public class LowestCommonAncestor {
    public static void main(String[] args) {

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LinkedList<TreeNode> path1 = new LinkedList<>();
        LinkedList<TreeNode> path2 = new LinkedList<>();
        find(root, p, path1);// 寻找从根节点到p的路径
        find(root, q, path2);// 寻找从根节点到q的路径
        // 从两个路径中找第一个不相等的节点或者第一个公共节点
        for (int i = 0; i < Math.min(path1.size(), path2.size()); ++i) {
            TreeNode node1 = path1.get(i);
            TreeNode node2 = path2.get(i);
            if (node1 != node2) return path1.get(i - 1);
            if (node1 == p || node1 == q) {
                return node1;
            }
        }
        return null;
    }

    private void find(TreeNode root, TreeNode p, LinkedList<TreeNode> path) {
        if (root == null) return;
        path.add(root);
        if (root == p) {
            return;
        }
        if (root.left != null) {// 在左子树中找
            find(root.left, p, path);
        }
        if (path.peekLast() == p) {// 在左子树中找到了
            return;
        }
        if (root.right != null) {// 在右子树中找
            find(root.right, p, path);
        }
        if (path.peekLast() == p) {// 在右子树中找到了
            return;
        }
        path.pollLast();// 回溯
    }
}

// 递归
class Solution1 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
}